The advent of digital technology and the rapid development of microprocessor technology gave rise to a demand for programmable logic. A PLD (“programmable logic device”) is an integrated circuit whose logic function is defined by the user by means of programming. A PLD is an architecture for digital logic operations with a plurality of switches that enable a multiplicity of signal paths. The logic function assigned to a PLD in a user-specific fashion is defined by means of configuration of the PLD.
PLDs include, inter alia, field-programmable gate arrays (FPGA), the functionality of which can be assigned to them by the user, mask-programmable gate arrays (MPGA, also called “structured ASICs”), which can be allocated a logic function by means of hardware configuration. Via-programmable gate arrays (VPGAs) are included among MPGAs.
Basic cells for a field-programmable gate array (FPGAs) and a structured ASIC (sASIC) provide combinatorial functionality and registers for implementing a design. A basic cell is intended to ensure a good mappability both of simple and of complex logic functions without generating unnecessary overhead.
A digital logic cell maps n input signals onto an output signal. The number of possible mapping functions is 22n. A circuit group as a digital logic cell is realized in accordance with the prior art for example using so-called look-up tables (LUT). For this purpose, function values of the logic function are set by means of a data word of 2n bits. In other words, the respectively logic function is coded into a data word. n input signals a0, a1 . . . an−1 are combined with one another in accordance with the selected logic function. Consequently, the logic input signals of the logic function y=f (a0, a1, . . . , an−1) may be regarded as a binary address.
An FPGA based on a look-up table (LUT) is disclosed in U.S. Pat. No. 6,529,040 B1, for example.
A logic basic cell for field-programmable gate arrays (FPGA) and “structured ASICs” provide combinatorial functionality for implementing a logic design.
The prior art discloses fine-granularity and coarse-granularity approaches for logic basic cells.
In the case of a fine-granularity basic cell, it is often not possible to realize all the possible 22n logic functions of n input signals, so that in some scenarios logic functions of low complexity already have to be realized in a manner distributed over a plurality of basic cells. Interconnect resources are blocked in this way, which leads to a less effective utilization of resources. Furthermore, in the case of such fine-granularity basic cells, long signal paths are disadvantageous in the case of more complex functions. Furthermore, the software for the partitioning of such fine-granularity basic cell arrangements is complex.
A coarse-granularity approach involves realizing a complex basic cell by means of which it is often possible for logic functions also of medium complexity to be realized completely. On the other hand, if a short data path is intended to be mapped onto such a coarse-granularity basic cell, large portions of the combinatorial resources of the basic cell are unutilized, with the result that the mapping is inefficient. Furthermore, the scalability of known basic cells is often unsatisfactory, particularly if a logic function to be mapped does not match a basic cell.
U.S. Pat. No. 6,331,789 B2 discloses a logic array apparatus with an array of programmable logic cells, having a plurality of inputs and a plurality of outputs and adapted connecting structures which are superposed on a portion of the programmable cell.
Inputs may serve as control inputs for a multiplexer tree, see Wannemacher, M “Das FPGA-Kochbuch”, [“The FPGA Cookbook”], fig. 7.36: logic block (CLB) of the XC4000 families, 1st edition, International Thomson Publishing Company, Bonn, 1998, p. 197. The multiplexers may be realized in a logic-based fashion and/or on the basis of transmission gates.
U.S. 2003/0206036 A1 discloses a user-defined configurable and programmable logic basic cell arrangement based on an interconnection of look-up tables and multiplexers.
U.S. 2002/0043988 A1 discloses a programmable logic basic cell arrangement having 5 data signal inputs and also a first logic function block and a second logic function block, implemented as a look-up table, a logic function configuration input and also a first multiplexer. At the data signal outputs, it is possible to tap off separately a signal at the output of the first logic function block, a signal at the output of the second logic function block and a signal at the output of the multiplexer.
EP 0 701 328 A2 discloses a field-programmable gate array (FPGA) having a decoder circuit arrangement for increasing the number of inputs for each programmable logic cell. The decoder circuit arrangement couples the respective desired look-up table of a respective logic cell.
EP 1 150 431 A1 discloses another FPGA with look-up tables.
U.S. Pat. No. 5,386,156 describes a programmable function unit set up for use in an FPGA, so-called ripple logic being used in the programmable function unit.
Furthermore, WO 02/093745 A2 discloses a reconstructable logic apparatus with a look-up table.
Many logic basic cells disclosed in the prior art are based on Boolean logic. Such logic basic cells make use of the fact that a function f(an, an−1, . . . , a0) of n+1 input signals ai, in accordance with Boolean logic, can be reduced to two functions f0, f1 of in each case n input signals ai as follows:f: IBn+1→IB: f(an, an−1, . . . , a1, a0)=ān·f0(an−1, . . . , a0)an·f1(an−1, . . . , a0)=fs(f1, f0, an)  (1)
The decomposition of f into f1 and f0 in accordance with equation (1) is referred to as so-called Shannon decomposition. In this case, an is the logic inverse of the data signal an. For the case n=2, that is to say where a function of n+1=3 input signals, the logic overall function f as a function of three input signals is thus reduced to two (simpler) logic subfunctions f0 and f1 of two input signals. Each of the logic subfunctions f0, f1 can be realized by one of the logic function blocks of a logic basic cell.
For the special case of n+1=4 input signals, using equation (1), the logic overall function can be reduced to two functions of three input signals, it being possible for each function of three input signals once again to be divided into two logic subfunctions with two inputs by applying equation (1) again. In other words, a logic overall function of four data signals can be decomposed into four logic subfunctions which can be realized by four logic function blocks, that is to say two logic basic cells. This consideration can be continued for an arbitrary number of input signals; by way of example, the realization of a logic overall function of five data signals requires 2*2*2=8 logic function blocks, that is to say four logic basic cells having in each case two logic function blocks.
However, a logic basic cell realized in accordance with the Shannon decomposition in accordance with equation (1) is not well suited to many applications requiring a high degree of flexibility.